#include <iostream>
#include <vector>
#include <string>
#include <gtest/gtest.h>

using namespace std; 

class Solution 
{

typedef unsigned long long int lli; 

public:

int check_valid(const string & A, lli i, lli j)
{
    // check for valid brackets 
    int multiply_factor = 1;    

    if (A[i] == '(' && A[j] == ')')
        return multiply_factor; 
    if (A[i] == '?' && A[j] == ')')
        return multiply_factor; 
    if (A[i] == '(' && A[j] == '?')
        return multiply_factor; 
        
    if (A[i] == '[' && A[j] == ']')
        return multiply_factor; 
    if (A[i] == '?' && A[j] == ']')
        return multiply_factor; 
    if (A[i] == '[' && A[j] == '?')
        return multiply_factor; 
        
    if (A[i] == '{' && A[j] == '}')
        return multiply_factor; 
    if (A[i] == '?' && A[j] == '}')
        return multiply_factor; 
    if (A[i] == '{' && A[j] == '?')
        return multiply_factor; 
    
    if (A[i] == '?' && A[j] == '?')
    {
        multiply_factor = 3; 
        return multiply_factor;
    }
         
    multiply_factor = 0; 
        
    return multiply_factor; 
}

lli recurse_count(const string & A, vector<vector<lli>> & dp, lli start, lli end)
{
    // base case 
    if (start > end)
        return 1; 
    // if value is already in dp 
    if (dp[start][end] != INT_MAX)
        return dp[start][end];
    
    int multiply_factor = 0;
    lli sum = 0; 
    // start must be a pair with some element in range [start + 1, end]
    for (lli i = start + 1; i <= end; ++i)
    {
        // assume start, i are a valid pair 
        multiply_factor = check_valid(A, start, i);
        if (multiply_factor != 0)
        {
            sum += multiply_factor * recurse_count(A, dp, start + 1, i - 1) * recurse_count(A, dp, i + 1, end); 
        }
    }
    dp[start][end] = sum;
    return dp[start][end]; 
}

int solve(string A) {
    vector<vector<lli>> dp(A.size(), vector<lli>(A.size(), INT_MAX)); 
    int answer = recurse_count(A, dp, 0, A.size() - 1) % (lli)pow(10, 9); 
    return answer; 
}

}; 

TEST(TestSolution, SimpleTest)
{
    const string A = "??}(??";
    Solution s; 
    EXPECT_EQ(s.solve(A), 3) << "wrong answer";
}

int main()
{
    testing::InitGoogleTest();
    return RUN_ALL_TESTS();
}

